package basic.courseLearn12.problem;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Stack;

//使用单调栈求解，数组找每个数左右离得最近的比自己大的数，没有的话就为null
public class LeftOrRightMax {

    @Test
    public void test(){
        int[] nums = {3,1,4,2,5};
        Integer[] nexts = humdrumStack(nums);
        for(int i=0;i<nexts.length;i++){
            System.out.print(nexts[i]+" ");
        }
    }


    /**
     * 单调栈求解
     * @param nums 数组
     * @return 所求数组
     */
    public Integer[] humdrumStack(int[] nums){
        //1. 定义返回数组
        Integer[] nexts = new Integer[nums.length*2];
        //2. 定义单调栈
        Stack<LinkedList<Integer>> stack = new Stack<LinkedList<Integer>>();
        //3. 遍历数组
        for(int i=0;i<nums.length;i++){
            if(stack.isEmpty()){  //3.1 栈空情况
                LinkedList<Integer> linkedList = new LinkedList<Integer>();
                linkedList.add(i);
                stack.push(linkedList);
            }else{  //3.2 栈非空情况
                //3.2.1 栈顶元素
                Integer topIndex =  stack.peek().getLast();
                //3.2.2 判断
                if(nums[i] == nums[topIndex]){
                    LinkedList<Integer> tempList = stack.peek();
                    tempList.add(i);
                    stack.pop();
                    stack.push(tempList);
                }else if(nums[i] > nums[topIndex]){
                    //循环弹出比nums[i]小的元素
                    while(!stack.isEmpty() && nums[i] > nums[stack.peek().getLast()]){
                        LinkedList<Integer> tempList = stack.pop();
                        while(!tempList.isEmpty()){
                            Integer index = tempList.pop();
                            Integer leftIndex = (stack.isEmpty())?null:stack.peek().getLast();
                            nexts[index*2] = leftIndex;//左侧
                            nexts[index*2+1] = i;
                        }
                    }
                    if (stack.isEmpty()){
                        LinkedList<Integer> linkedList = new LinkedList<Integer>();
                        linkedList.add(i);
                        stack.push(linkedList);
                        continue;
                    }
                    //等于情况
                    if(nums[i] == nums[stack.peek().getLast()]){
                        LinkedList<Integer> tempList = stack.peek();
                        tempList.add(i);
                        stack.pop();
                        stack.push(tempList);
                    }else{  //小于情况
                        LinkedList<Integer> linkedList = new LinkedList<Integer>();
                        linkedList.add(i);
                        stack.push(linkedList);
                    }
                }else{  //3.2.3 小于栈顶元素
                    LinkedList<Integer> linkedList = new LinkedList<Integer>();
                    linkedList.add(i);
                    stack.push(linkedList);
                }
            }
        }
        //4. 循环弹出剩余元素
        while(!stack.isEmpty()){
            LinkedList<Integer> tempList = stack.pop();
            while(!tempList.isEmpty()){
                Integer index = tempList.pop();
                Integer leftIndex = (stack.isEmpty())?null:stack.peek().getLast();
                nexts[index*2] = leftIndex;//左侧
                nexts[index*2+1] = null;
            }
        }
        return nexts;


    }

}
